package sword_offer;

import common.ListNode;

/**
 * @ClassName _22KthNodeFromEnd
 * @Description: 获取链表中倒数第n个节点
 * @Author: yongliang.ma
 * @Create_time:2022/10/9 13:40
 */
public class _22KthNodeFromEnd {

    // 1、遍历两次：第一次遍历记录总数，就可以得到正数第几个数字，第二遍遍历中直接定位到对应位数的数字即为所求。

    // 2、遍历一次：设计两个指针，快慢指针，快指针先行移动k步，然后慢指针开始移动，等到快指针移动到末尾的时候慢指针的位置即为所求

    // Tips：考虑k比链表中节点数目多的情况
    public ListNode getKthFromEnd(ListNode head, int k){
        // 设计快慢指针，slowIndex, fastIndex
        ListNode fastCursor = head, slowCursor = head;
        while (k > 0){
            if (fastCursor == null)
                return null;
            fastCursor = fastCursor.next;
            k--;
        }
        while (fastCursor != null){
            fastCursor = fastCursor.next;
            slowCursor = slowCursor.next;
        }

        return slowCursor;
    }
}
